package com.zhugang.week13.sorting;

import org.junit.Assert;
import org.junit.Test;

import java.lang.reflect.InvocationTargetException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import static java.util.stream.Collectors.toList;

/**
 * 循环不变式、递归、映射(hash)
 */
public class SortTests {

    @Test
    public void test_insertionSort() {
        sortTest(InsertionSort.class, 100_000);
    }

    @Test
    public void test_selectionSort() {
        sortTest(SelectionSort.class, 100_000);
    }

    @Test
    public void test_bubbleSort() {
        sortTest(BubbleSort.class, 100000);
    }


    @Test
    public void test_mergeSort() {
        sortTest(MergeSort.class, 100000);
    }

    @Test
    public void test_quickSort() {
        sortTest(QuickSort.class, 100000);
    }


    @Test
    public void test_quicksort1() {
        sortTest(QuickSort2.class, 100000);
    }

    @Test
    public void test_quicksort() {
        sortTest(QuickSort.class, 1000000);
    }

    @Test
    public void test_bucketSort() {
        var bucketSort = new BucketSort();
        ArrayList<Integer> l = new ArrayList<>();

        for (int i = 0; i < 1000000; i++) {
            l.add((int) (Math.random() * 100));
        }
        var start = System.currentTimeMillis();
        List<Integer> A = bucketSort.sort(l);
        System.out.println("time:" + (System.currentTimeMillis() - start));
        assertSorted(A);
    }


    public void sortTest(Class cls, int N) {
        try {
            var constructor = cls.getConstructor();
            var rawInst = constructor.newInstance();
            var start = System.currentTimeMillis();
            if (rawInst instanceof IIMutableSorter) {
                var A = gen(N);
                var inst = (IIMutableSorter) rawInst;
                // 调用排序方法
                A = inst.sort(A);
                System.out.println("time usage:" + (System.currentTimeMillis() - start));
                assertSorted(A);

            } else if (rawInst instanceof IMutableSorter) {
                var A = gen(N).stream().mapToInt(x -> x).toArray();
                var inst = (IMutableSorter) rawInst;
                // 调用排序方法
                inst.sort(A);
                System.out.println("time usage:" + (System.currentTimeMillis() - start));
                assertSorted(A);
            }
        } catch (NoSuchMethodException e) {
            e.printStackTrace();
        } catch (IllegalAccessException e) {
            e.printStackTrace();
        } catch (InstantiationException e) {
            e.printStackTrace();
        } catch (InvocationTargetException e) {
            e.printStackTrace();
        }
    }

    static void assertSorted(int[] A) {
        assertSorted(Arrays.stream(A).boxed().collect(toList()));
    }

    static void assertSorted(List<Integer> A) {
        Integer o = Integer.MIN_VALUE;
        for (var i : A) {
            // 比较相邻元素是否有序
            if (o > i) {
                System.out.println(A.toString());
                Assert.fail("Array not in sorted order");
            }
            o = i;
        }
    }

    static List<Integer> gen(int n) {
        var A = new ArrayList<Integer>();
        for (int i = 0; i < n; i++) {
            A.add((int) (Math.random() * n));
        }
        return A;
    }
}
